//
// Created by Administrator on 2021/5/29.
//
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int subarraySum(vector<int> &nums, int k) {
        // 前缀和 + hash
        // hash 储存前缀和及出现的个数
        unordered_map<int, int> um;
        // 默认存在前缀和为0的 1个
        um[0] = 1;
        int pre = 0, ans = 0;
        for (auto &x:nums) {
            // 更新前缀和
            pre += x;
            // 两个前缀和之间的差为k 说明中间存在和为k的
            if (um.find(pre - k) != um.end()) ans += um[pre - k];
            // 更新这个前缀和的个数
            ++um[pre];
        }
        return ans;
    }
};

int main() {
    vector<int> v{1, 1, 1};
    Solution sol;
    cout << sol.subarraySum(v, 2) << endl;
    return 0;
}